package 二叉树;

import java.util.Deque;
import java.util.LinkedList;

public class 对称二叉树 {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*
    递归法
     */
    public boolean isSymmetric1(TreeNode root){
       return compare(root.left,root.right);
    }
    public boolean compare(TreeNode left,TreeNode right){
        if (left == null && right != null){
            return false;
        }
        if (left != null && right == null){
            return false;
        }
        if (left == null && right == null){
            return true;
        }
        if (left.val!=right.val){
            return false;
        }
        //比较外侧
        boolean compareOutside = compare(left.left, right.right);
        //比较内侧
        boolean compareInside = compare(left.right, right.left);
         return compareInside&&compareOutside;
    }



    /*
    迭代法 使用双端队列
     */

    public boolean isSymmetric2(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()){
            TreeNode leftnode = deque.pollFirst();
            TreeNode rightnode = deque.pollLast();
            if (leftnode == null && rightnode == null){
                continue;
            }
            if (leftnode==null||rightnode==null||leftnode.val!=rightnode.val) return false;
            //判断外侧
            deque.offerFirst(leftnode.left);
            deque.offerFirst(rightnode.right);
            //判断内侧
            deque.offerLast(leftnode.right);
            deque.offerLast(rightnode.left);


        }
        return true;

    }

    /*
    迭代法 使用普通队列
     */

    public boolean isSymmetric3(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while(!deque.isEmpty()){
            TreeNode leftNode  = deque.poll();
            TreeNode rightNode  = deque.poll();
            if (leftNode == null && rightNode == null){
                continue;
            }
            if (leftNode == null || rightNode == null || leftNode.val!=rightNode.val ) return false;
            //这里因为是普通队列 所以顺序和用双端队列的不同
            //主要也还是先判断外侧 再判断内侧
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }

        return true;

    }



}
